package practice11;

/**
 * # 问题描述
 * <p>
 * 实现一个基本的计算器来计算一个简单的字符串表达式的值。注意事项如下：
 * <p>
 * - 输入是一个字符串表达式（可以假设所给定的表达式都是有效的）
 * <p>
 * - 字符串表达式可以包含的运算符号为：左括号 `(`, 右括号 `)`, 加号 `+`, 减号 `-`
 * <p>
 * - 可以包含的数字为：非负整数（< 10）
 * <p>
 * - 字符串中不包含空格
 * <p>
 * - 处理除法 case 的时候，可以直接省略小数部分结果，只保留整数部分参与后续运算
 * <p>
 * - 请不要使用内置的库函数 `eval`
 * <p>
 * ## 输入格式
 * <p>
 * 如：`3+4*5/(3+2)`
 * <p>
 * ## 数据约束
 * <p>
 * 见题目描述
 * <p>
 * ## 输出格式
 * <p>
 * 计算之后的数字
 * <p>
 * **输入样例**：
 * - `1+1`
 * - `3+4*5/(3+2)`
 * - `4+2*5-2/1`
 * - `(1+(4+5+2)-3)+(6+8)`
 * <p>
 * **输出样例**：
 * - `2`
 * - `7`
 * - `12`
 * - `23`
 */

import java.util.Stack;

public class Main {
    public static int solution(String expression) {
        // 创建两个栈，一个用于存储数字，一个用于存储运算符
        Stack<Integer> numStack = new Stack<>();
        Stack<Character> opStack = new Stack<>();

        // 遍历表达式中的每一个字符
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);

            // 如果当前字符是数字
            if (Character.isDigit(c)) {
                // 将字符转换为整数并压入数字栈
                numStack.push(c - '0');
            }
            // 如果当前字符是左括号
            else if (c == '(') {
                // 将左括号压入运算符栈
                opStack.push(c);
            }
            // 如果当前字符是右括号
            else if (c == ')') {
                // 不断从运算符栈中弹出运算符并执行相应的运算，直到遇到左括号
                while (!opStack.isEmpty() && opStack.peek() != '(') {
                    performOperation(numStack, opStack);
                }
                // 弹出左括号，但不进行任何操作
                opStack.pop();
            }
            // 如果当前字符是运算符
            else {
                // 不断从运算符栈中弹出运算符并执行相应的运算，直到栈顶运算符的优先级低于当前运算符
                while (!opStack.isEmpty() && precedence(opStack.peek()) >= precedence(c)) {
                    performOperation(numStack, opStack);
                }
                // 将当前运算符压入运算符栈
                opStack.push(c);
            }
        }

        // 处理运算符栈中剩余的运算符
        while (!opStack.isEmpty()) {
            performOperation(numStack, opStack);
        }

        // 数字栈中最后一个元素即为表达式的计算结果
        return numStack.pop();
    }

    // 执行一次运算，并将结果压回数字栈
    private static void performOperation(Stack<Integer> numStack, Stack<Character> opStack) {
        // 检查栈是否为空，防止空指针异常
        if (numStack.size() < 2 || opStack.isEmpty()) return;

        // 从数字栈中弹出两个数字，b 是第二个弹出的，a 是第一个弹出的
        int b = numStack.pop();
        int a = numStack.pop();

        // 从运算符栈中弹出一个运算符
        char op = opStack.pop();

        // 根据运算符执行相应的运算
        switch (op) {
            case '+':
                // 执行加法运算并将结果压回数字栈
                numStack.push(a + b);
                break;
            case '-':
                // 执行减法运算并将结果压回数字栈
                numStack.push(a - b);
                break;
            case '*':
                // 执行乘法运算并将结果压回数字栈
                numStack.push(a * b);
                break;
            case '/':
                // 执行除法运算并将结果压回数字栈（整数除法）
                numStack.push(a / b);
                break;
        }
    }

    // 获取运算符的优先级
    private static int precedence(char op) {
        switch (op) {
            case '+':
            case '-':
                // 加法和减法的优先级为 1
                return 1;
            case '*':
            case '/':
                // 乘法和除法的优先级为 2
                return 2;
            default:
                // 其他字符的优先级为 0
                return 0;
        }
    }

    public static void main(String[] args) {
        // 测试几个示例表达式
        System.out.println(solution("1+1")); // 输出 2
        System.out.println(solution("3+4*5/(3+2)")); // 输出 7
        System.out.println(solution("4+2*5-2/1")); // 输出 12
        System.out.println(solution("(1+(4+5+2)-3)+(6+8)")); // 输出 23
    }
}